{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Using PyVRP's components\n",
    "\n",
    "We have relied on the `Model` interface to solve VRP instances in the examples so far.\n",
    "That high-level interface hides a lot of the components that available in PyVRP, which uses [a hybrid genetic search algorithm](https://pyvrp.org/setup/introduction_to_hgs.html) under the hood.\n",
    "In this notebook we will investigate these components in more detail to build our own `solve` function based on hybrid genetic search.\n",
    "\n",
    "Along the way we will solve the `RC208.vrp` instance, one of the well-known VRPTW benchmark instances of Solomon.\n",
    "This instance consists of 100 clients."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pyvrp import read\n",
    "\n",
    "INSTANCE = read(\"data/RC208.vrp\", \"dimacs\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will implement a `solve()` function that will take a `stop` stopping criterion, and a `seed` for the random number generator.\n",
    "This definition is very close to that of `Model.solve`.\n",
    "The signature is\n",
    "```python\n",
    "def solve(stop: StoppingCriterion, seed: int) -> Solution: ...\n",
    "```"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A tour of PyVRP\n",
    "\n",
    "We need to understand the separate components in PyVRP before we are ready to implement this function.\n",
    "PyVRP uses a hybrid genetic search algorithm under the hood.\n",
    "The `GeneticAlgorithm` object manages a population of solutions.\n",
    "In each iteration, two solutions are selected from this population for *crossover* using a crossover operator from `pyvrp.crossover`, which generates a new offspring solution.\n",
    "That offspring solution is then improved using a method from `pyvrp.search`.\n",
    "The improved offspring solution is then added to the population.\n",
    "This process continues until a stopping condition is reached (see `pyvrp.stop` for different conditions).\n",
    "Let's have a look at the different parts of `pyvrp` that implement this algorithm."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To instantiate the `GeneticAlgorithm`, we first need to specify an (initial) population, search method, penalty manager and random number generator.\n",
    "Let's start with the random number generator because it is the easiest to set up.\n",
    "\n",
    "##### Random number generator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pyvrp import RandomNumberGenerator\n",
    "\n",
    "rng = RandomNumberGenerator(seed=42)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Search method\n",
    "\n",
    "Let's now define the search method.\n",
    "PyVRP currently implements a `LocalSearch` method that is very customisable with different operators and search neighbourhoods.\n",
    "Different operators search different parts of the solution space, which can be beneficial in finding better solutions.\n",
    "The neighbourhood defines which edges are evaluated.\n",
    "By restricting that set of edges the local search method works much faster.\n",
    "\n",
    "We provide default operator sets and neighbourhoods, which can be used as follows.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pyvrp.search import (\n",
    "    LocalSearch,\n",
    "    NODE_OPERATORS,\n",
    "    ROUTE_OPERATORS,\n",
    "    compute_neighbours,\n",
    ")\n",
    "\n",
    "neighbours = compute_neighbours(INSTANCE)\n",
    "ls = LocalSearch(INSTANCE, rng, neighbours)\n",
    "\n",
    "for node_op in NODE_OPERATORS:\n",
    "    ls.add_node_operator(node_op(INSTANCE))\n",
    "\n",
    "for route_op in ROUTE_OPERATORS:\n",
    "    ls.add_route_operator(route_op(INSTANCE))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Solution representation and evaluation\n",
    "\n",
    "We now have a functioning local search method.\n",
    "All we need are two additional components to make it work: a `Solution` that described a set of routes, and a `CostEvaluator` that can be used to evaluate different moves.\n",
    "Let's define those."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pyvrp import Solution, CostEvaluator\n",
    "\n",
    "cost_evaluator = CostEvaluator(load_penalty=20, tw_penalty=20, dist_penalty=0)\n",
    "sol = Solution.make_random(INSTANCE, rng)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The random solution `sol` that we created just yet is not feasible.\n",
    "This is not a problem, because PyVRP internally uses penalties to evaluate infeasibilities in each solution.\n",
    "This is done using the `CostEvaluator`'s `penalised_cost` function, which allows us to determine the quality of infeasible solutions as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert not sol.is_feasible()\n",
    "print(cost_evaluator.penalised_cost(sol))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see if the local search can improve this solution further."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_sol = ls.search(sol, cost_evaluator)\n",
    "\n",
    "assert not sol.is_feasible()\n",
    "print(cost_evaluator.penalised_cost(new_sol))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Much better! \n",
    "But the new solution is not yet feasible.\n",
    "Can we hammer out the infeasibilities by increasing the penalties?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cost_evaluator = CostEvaluator(200, 200, 0)\n",
    "new_sol = ls.search(sol, cost_evaluator)\n",
    "\n",
    "assert new_sol.is_feasible()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How good is this solution?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(cost_evaluator.penalised_cost(new_sol))"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pretty good!\n",
    "This is how PyVRP manages infeasibilities: it adjusts the penalty parameters to ensure sufficiently many solutions are feasible.\n",
    "Too few feasible solutions and the penalties go up; too many and they go down.\n",
    "This ensures a balanced population of feasible and infeasible solutions, which is good for diversity and crossover.\n",
    "\n",
    "The object in charge of managing the penalty terms is the `PenaltyManager`, which can be asked to provide a `CostEvaluator` of the form we saw above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pyvrp import PenaltyManager\n",
    "\n",
    "pen_manager = PenaltyManager()\n",
    "cost_evaluator = pen_manager.cost_evaluator()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Population management\n",
    "\n",
    "We are nearly there.\n",
    "All we still need to provide is a `Population`, and a set of initial (random) solutions.\n",
    "Let's tackle the `Population`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pyvrp import Population\n",
    "from pyvrp.diversity import broken_pairs_distance\n",
    "\n",
    "pop = Population(broken_pairs_distance)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The population tracks the diversity of its solutions.\n",
    "Computing the diversity (dissimilarity) of two solutions can be done in several ways.\n",
    "Functions to do so are provided in `pyvrp.diversity`, and can be provided to the `Population`.\n",
    "Here, we use the `broken_pairs_distance`, which computes a number in $[0, 1]$ based on the number of dissimilar edges in the solutions.\n",
    "\n",
    "A new population starts off empty:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert len(pop) == 0"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can add new solutions to the population using `Population.add`.\n",
    "Recall that `sol` and `new_sol` are, respectively, infeasible and feasible solutions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert not sol.is_feasible()\n",
    "pop.add(sol, cost_evaluator)\n",
    "\n",
    "assert new_sol.is_feasible()\n",
    "pop.add(new_sol, cost_evaluator)\n",
    "\n",
    "assert len(pop) == 2\n",
    "assert pop.num_feasible() == 1\n",
    "assert pop.num_infeasible() == 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### The genetic algorithm and crossover"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A set of initial solution can be constructed easily, by generating a list of random solutions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "init_sols = [Solution.make_random(INSTANCE, rng) for _ in range(25)]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are now ready to construct the genetic algorithm.\n",
    "This object additionally takes a crossover operator from `pyvrp.crossover`.\n",
    "We will use the selective route exchange (SREX) method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pyvrp import GeneticAlgorithm\n",
    "from pyvrp.crossover import selective_route_exchange as srex\n",
    "\n",
    "algo = GeneticAlgorithm(\n",
    "    INSTANCE,\n",
    "    pen_manager,\n",
    "    rng,\n",
    "    pop,\n",
    "    ls,\n",
    "    srex,\n",
    "    init_sols,\n",
    ")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can call `algo.run`, which iterates until a stopping criterion is met.\n",
    "These stopping criteria can be imported from `pyvrp.stop` - see [the API documentation](https://pyvrp.org/api/stop.html) for details."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pyvrp.stop import MaxIterations, MaxRuntime\n",
    "\n",
    "iter_res = algo.run(stop=MaxIterations(500))\n",
    "time_res = algo.run(stop=MaxRuntime(1))  # seconds"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's investigate the solutions!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(iter_res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(time_res)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The `solve` function\n",
    "\n",
    "Let's put everything we have learned together into a `solve` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve(stop, seed):\n",
    "    rng = RandomNumberGenerator(seed=seed)\n",
    "    pm = PenaltyManager()\n",
    "    pop = Population(broken_pairs_distance)\n",
    "\n",
    "    neighbours = compute_neighbours(INSTANCE)\n",
    "    ls = LocalSearch(INSTANCE, rng, neighbours)\n",
    "\n",
    "    for node_op in NODE_OPERATORS:\n",
    "        ls.add_node_operator(node_op(INSTANCE))\n",
    "\n",
    "    for route_op in ROUTE_OPERATORS:\n",
    "        ls.add_route_operator(route_op(INSTANCE))\n",
    "\n",
    "    init = [Solution.make_random(INSTANCE, rng) for _ in range(25)]\n",
    "    algo = GeneticAlgorithm(INSTANCE, pm, rng, pop, ls, srex, init)\n",
    "\n",
    "    return algo.run(stop)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Very good.\n",
    "Let's solve the instance again, now using the `solve` function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "res = solve(stop=MaxIterations(1000), seed=1)\n",
    "print(res)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "PyVRP also provides many plotting tools that can be used to investigate a data instance or solution result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from pyvrp.plotting import plot_result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig = plt.figure(figsize=(12, 8))\n",
    "\n",
    "plot_result(res, INSTANCE, fig=fig)\n",
    "plt.tight_layout()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The top-left figure shows the average diversity of the feasible and infeasible populations.\n",
    "The periodic spikes are due to survivor selection: when the population grows too large, bad solutions are purged.\n",
    "It is clear from this figure that periodic survivor selection improves diversity.\n",
    "The middle-left figure shows the best and average objectives of both sub-populations, which improve over time as the search progresses.\n",
    "The bottom-left figure shows average iteration runtimes (in seconds).\n",
    "Finally, the figure on the right plots the best observed solution."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion\n",
    "\n",
    "In this notebook we have used some of the different components in PyVRP to implement our own `solve` function.\n",
    "Along the way we learned about how PyVRP works internally.\n",
    "\n",
    "The components we saw in this notebook can also be used to create different search algorithms altogether.\n",
    "For example, our `LocalSearch` search method could be used to quickly implement an iterated local search scheme.\n",
    "This modularity allows for a lot of reuse of the PyVRP package."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
